Field of the Invention
The invention relates to a method for generating sequences of random numbers of a 1/f noise.
Random numbers of a 1/f noise can be used, for example, in a transient circuit simulation which takes account of noise, influences. A 1/f noise is understood as a stochastic process with a specific frequency spectrum which can be described by the equation                                           S            ⁡                          (              f              )                                ∝                      1                          f              β                                      ,                  β          ∈                    ]        ⁢    0    ,      1    [  
1/f noise sources are suitable for modeling noise influences in a multiplicity of technical and physical systems, and for systems for estimating and predicting events on the financial markets. In particular, many electronic components such as, for example, pn diodes and MOS field effect transistors have 1/f noise sources.
It is possible to approximate 1/f noise sources by carrying out a summation of the effects of many noise sources which respectively have a Lorentz spectrum as frequency spectrum. Such noise sources can be modeled, for example, by the system response of a linear time-invariant system which can also be denoted as an LTI system, at whose system input a white noise is applied. It is disadvantageous in this procedure that the dimension of the system of differential equations to be solved numerically is inflated beyond bounds. This results in long computing times and a high storage requirement for a computer system which is used to simulate a system which is subject to the influence of a 1/f noise.
It is the object of the invention to specify a method for generating a sequence of random numbers of a 1/f noise which can be carried out quickly and with a low computational outlay. It is also the object of the invention to specify an improved method for simulating a technical system which is subject to a 1/f noise. Finally, the aim is also to specify a computer program for determining sequences of random numbers of a 1/f noise which can be carried out quickly and which requires only few resources of a computer system.
This object is achieved by means of the subject matters of the independent patent claims. Improvements follow from the respective subclaims.
In accordance with an idea on which the invention is based, the numerical integration of a system path of a system which is subject to 1/f noise influences is reduced in the case of a constant integration step size to the simulation of sequences of suitably correlated random numbers. A batch method is used in order to generate sequences of such random numbers. In this context, the term xe2x80x9cbatch methodxe2x80x9d is understood to mean that the length of the sequence of the random numbers may be arbitrary. However, the random numbers must be prescribed when the method is started, the overall random number sequence being generated in a first computing step. It is possible using the method according to the invention to avoid inflation of the dimension of the system of differential equations to be solved numerically in the case of a constant integration step size. This results in considerable gains in computing time.
In accordance with a further idea on which the invention is based, the efficiency of the numerical determination of the dynamics of the simulated system is substantially raised by adaptive step size control. Specifically, the invention specifies a method which permits an adaptive step size control and a numerical simulation of 1/f noise sources to be combined with one another, it being possible for the simulation of 1/f noise to be incorporated into a transient system simulation with adaptively controlled step size. The invention permits the known methods for adaptive step size control to be combined with a numerical simulation of 1/f noise sources without the system dimension being inflated. The procedure for this purpose is a two-stage method. In a first stage, the system dynamics are integrated numerically using an adaptive step size control, the 1/f noise sources not yet being taken into account. The adaptive step sizes determined in the process serve as the basis of a second integration pass in which account is taken of the 1/f noise sources whose proportions are determined with the aid of the information obtained in the first stage of the simulation. Thus, in the case of the transient simulation of a system the invention renders it possible to use the advantages of adaptive step size control together with a simplified numerical simulation of 1/f noise sources. This produces an increased numerical approximation quality of the simulation in conjunction with efficient use of the available computing time resources, inflation of the system dimension being avoided.
In accordance with the invention, the problem of noise simulation in modeling the system to be simulated is converted into the problem of generating a random number sequence. In accordance with the invention, the correlations of these random numbers are determined, and this is used for simple and accurate generation of the corresponding random number sequences.
The methods according to the invention for generating a sequence of random numbers of a 1/f noise provide as steps, in particular, the formation of a covariance matrix C from which the Cholesky decomposition L is subsequently formed. The covariance matrix C differs in this process in the case in which a constant simulation step size xcex4 is used from the case in which an adaptive step size is used.
For the case of a constant step size xcex4, the covariance matrix is determined element by element with knowledge of a desired spectral value xcex2, the number n of the random numbers, to be generated, of a 1/f noise and the intensity constant const, one element e(i,j) each of the covariance matrix C being determined using the following equation:
e(i,j)=const.|xcex4|xcex2+1xc2x7(|ixe2x88x92j+1|xcex2+1xe2x88x922|ixe2x88x92j|xcex2+1+|ixe2x88x92jxe2x88x921|xcex2+1)
where i,j=1, . . . , n.
The Cholesky decomposition L of the covariance matrix C is subsequently formed, C=Lxc2x7LT, L assuming the form of a triangular matrix in which only the diagonals and the lower half are occupied.
The Cholesky decomposition L thus found can now be used to generate arbitrarily many sequences of random numbers of a 1/f noise. A vector x of length n is firstly formed for this purpose from random numbers normally distributed in [0,1]. Such normally distributed random numbers have an expected value 0 and a variance 1. They can be determined in a known way by transformation from a vector, of equal length, of equally distributed random numbers.
The target vector y with the desired 1/f-distributed random numbers is then produced by multiplying the Cholesky decomposition L by the vector x.
In the method according to the invention, which permits an adaptive numerical solution of stochastic differential equations, the procedure is essentially as described above. However, by contrast with the mode of procedure described above it is not possible to assume a constant simulation step size xcex4. Rather, it is necessary firstly to calculate a step size vector xcex4 which results from prescribed instants of consideration t0xe2x88x92tn in the first step of the simulation. Thereafter, the covariance matrix C is set up by determining the elements thereof using the following equation:
e(i,j)=constxc2x7(xe2x88x92|tjxe2x88x92ti|xcex2+1+|tjxe2x88x921xe2x88x92ti|xcex2+1+|tjxe2x88x92tixe2x88x921|xcex2+1xe2x88x92|tjxe2x88x921xe2x88x92tixe2x88x921|xcex2xe2x88x921)
where i,j=1, . . . , n.
The concept of simulating 1/f noise is based on the following thinking. The dynamics of a system which is subject to stochastic influences is modeled adequately by a stochastic process. Individual random realizations (so-called paths) of the basic stochastic process are generally calculated numerically for the purpose of simulating such system dynamics. Paths of stochastic integrals of the form       ∫    0    t    ⁢            Y      ⁡              (        s        )              ⁢                  η                  1          f                    ⁡              (        s        )              ⁢          xe2x80x83        ⁢          ⅆ      s      
are calculated numerically in order to simulate systems with 1/f noise sources. Here, s (integration variable) and t (upper integration limit) denote the time,   η      1    f  
(s)ds denotes a 1/f noise source, and Y(s) denotes a stochastic process which describes the time dynamics of a variable, for example the electric voltage in the circuit simulation.
If BFBM(s) denotes that stochastic process whose derivation (mathematically: derivation in the distribution sense) yields the 1/f noise process   η      1    f  
(s), the stochastic integral to be calculated can be written as                                           ∫            0            t                    ⁢                                    Y              ⁡                              (                s                )                                      ⁢                                          η                                  1                  f                                            ⁡                              (                s                )                                      ⁢                          xe2x80x83                        ⁢                          ⅆ              s                                      =                              ∫            0            t                    ⁢                                    Y              ⁡                              (                s                )                                      ⁢                          ⅆ                                                B                  FBM                                ⁡                                  (                  s                  )                                                                                        (        1.1        )            
The integral of the right-hand side is to be interpreted as Riemann Stieltjes integral of the stochastic process Y(s) with the process BFBM(s) as integrator. This integral can be approximated by a sum by decomposing the integration interval [0,t] in accordance with 0=t0 less than t1 less than . . .  less than t=t into n disjoint subintervals [ti, tixe2x88x921], i=1, . . . n:                                           ∫            0            t                    ⁢                                    Y              ⁡                              (                s                )                                      ⁢                          ⅆ                                                B                  FBM                                ⁡                                  (                  s                  )                                                                    ≈                              ∑                          i              =              1                        n                    ⁢                      xe2x80x83                    ⁢                                    Y              ⁡                              (                                  t                                      i                    -                    1                                                  )                                      ⁡                          [                                                                    B                    FBM                                    ⁡                                      (                                          t                      i                                        )                                                  -                                                      B                    FBM                                    ⁡                                      (                                          t                                              i                        -                        t                                                              )                                                              ]                                                          (        1.2        )            
This sum is a random variable. The dependence on the result xcfx89 of the random experiment was consistently omitted.
A process BFBM(s) whose generalized derivation has a 1/f spectrum is known in the literature under the name of xe2x80x9cfractional Brownian motionxe2x80x9d. BFBM(s) is a Gaussian stochastic process, and as such is characterized completely by its expected value
E(BFBM(s))=O∀sxcex5Rxe2x80x83xe2x80x83(1.3)
and by its covariance function
xe2x80x83Cov(BFBM(s),BFBM(t))=constxc2x7(|s|xcex2+1+|t|xcex2+1xe2x88x92|txe2x88x92s|xcex2+1)xe2x80x83xe2x80x83(1.4)
The batch method according to the invention for generating suitable random numbers reduces the simulation of 1/f noise influences essentially to the generation of realizations of the random variables [BFBM(ti)xe2x88x92BFBM(tixe2x88x921)], that is to say of increases in the fractional Brownian motion.
For the purpose of the numerical solution of stochastic differential equations with   1      f    β  
noise sources, the step size of the numerical integration may constantly be set to the value xcex4 greater than 0, and a number nEN which stipulates the number of the time steps over which numerical integration is to performed may be (arbitrarily) selected.
For this constant step size and this fixed integration interval, the aim now is to generate the required correlated random numbers all at once, that is to say in the course of a batch method.
In order to calculate a path of the integral ∫0TY(s)dBFBM(s) approximately, there is a need in each case, in accordance with the above, to realize the random variables xcex94BFBM(i):=[BFBM(ixcex4)xe2x88x92BFBM((ixe2x88x921)xcex4)], i=1, . . . , n. The formulae (1.3) and (1.4) can be used to calculate the expected value, variance and covariance of these intercorrelated random variables:
E(xcex94BFBM(i))=0,i=1, . . . , nxe2x80x83xe2x80x83(2.5)
Var(xcex94BFBM(i))=2xc2x7constxc2x7|xcex4|xcex2+1,i=1, . . . , nxe2x80x83xe2x80x83(2.6)
Cov(xcex94BFBM(i),xcex94BFBM(j))=constxc2x7|xcex4|xcex2+1xc2x7(|ixe2x88x92j+1|xcex2+1xe2x88x922|ixe2x88x92j|xcex2+1+|ixe2x88x92jxe2x88x921|xcex2+1), i,j=1, . . . ,nxe2x80x83xe2x80x83(2.7)
Since the random variables xcex94BFBM(i) represent increases in a Gaussian stochastic process, the random variable vector (xcex94BFBM(1), . . . , xcex94BFBM(n)) is an n-dimensional Gaussian-distributed random variable, and is therefore completely determined by expected value, variance and covariance (in accordance with formulas (2.5) to (2.7)).
A batch method for respectively generating a realization of the correlated random variables xcex94BFBM(1), . . . , xcex94BFBM(n) is therefore as follows:
select a value of the coefficient const greater than 0 which parametrizes the intensity of the 1/f noise source generate a realization of an n-dimensional Gaussian normal distribution with the expected value 0 and covariance matrix
Covij=constxc2x7|xcex4|xcex2+1xc2x7(|ixe2x88x92j+1|xcex2+1xe2x88x922|ixe2x88x92j|xcex2+1└ixe2x88x92jxe2x88x921┘62 +1),i,j=1, . . . , nxe2x80x83xe2x80x83(2.8)
interpret the random number vector thus generated as a realization of the sequence of BFBM increases {xcex94BFBM(1), . . . , xcex94BFBM(n)}, and use this realization in accordance with section 1 for the numerical calculation of a stochastic path of time length nxc2x7xcex4.
It may be pointed out that a dedicated realization of the sequence {xcex94BFBM(1), . . . , xcex94BFBM(n)} must be calculated for each 1/f noise source in the system.
The following procedure is adopted in the case of the batch methods for the numerical solution of stochastic differential equations with   1      f    β  
noise sources in the case of an adaptive step size.
Firstly, an adaptive step size determination is carried out. The quality of the approximation (1.2) depends essentially on the decomposition of the integration interval [0,t] into disjoint subintervals [ti, tixe2x88x921], i=1, . . . , n. In the numerical solution of deterministic differential equations, there are methods for step size control which adapt the step sizexe2x80x94that is to say, the length of the currently processed subintervalxe2x80x94to the respective current time scale of the system dynamics, and thereby ensure that the available computing time is used as specifically as possible to increase the numerical approximation accuracy. A possible step size control is specified as follows:
Prescribe a tolerable local discretization error emax greater than 0.
Estimate the current local error elok (that is to say, the error contribution made to the approximation error which is generated in the current integration substep). This estimate can be performed in one of the following ways:
a) Repeat the last iteration step with half the step size, and form the difference between the two results.
b) Compare the result of the current method rule with the result of a method rule of higher error order (xe2x80x9cembeddingxe2x80x9d), for example by means of a Runge-Kutta method.
c) Direct approximation using a numerical difference quotient, for example, with the aid of polynomial interpolation.
If the estimated local error elok is greater than emax, the current step is abandoned, otherwise accepted (a posteriori estimator).
The step size of the next step is determined by comparing elok with emax. If elok less than emax, the step size is increased, otherwise reduced (a priori estimator). The estimation method for the local error elok can be selected variously for a priori and a posteriori estimators.
The present invention describes a method which renders it possible for the improvement in the approximation accuracy by means of step size control also to be used for the simulation of 1/f noise.
For this purpose, the numerical integration is carried out in 2 stages.
(A) In stage (A), the desired integration time t greater than 0 is prescribed, and the system dynamics are calculated neglecting the 1/f noise sources. This is performed by numerical solution of the system of ordinary (or algebroid) differential equations which describes the deterministic component of the system dynamics. During this stage A integration, use is made of a method for step size adaptation, for example, that described above. After the traversal of the stage A integration, the result of the step size adaptation is a sequence of accepted step sizes, and thus a subdivision of the integration interval [0, t ] into disjoint subintervals [ti, tixe2x88x921], i=1, . . . n. The number n of required subintervals is likewise a result of the step size control.
(B) The stage A integration is followed by a second numerical integration run which extends over the same integration interval [0, t ]. The 1/f noise sources are now also incorporated into the simulation of the system dynamics. Use is made as sole result of the integration run (A) of the discretization of the integration interval [0, t] into disjoint subintervals [ti, tixe2x88x921], i=1, . . . n, and the number n of required subintervals. The simulation of the system dynamics follows the concept presented above. In this case, the required realizations of the random variables [BFBM(ti)xe2x88x92BFBM(tixe2x88x921)] are generated using a method which is presented below.
Let there be given a subdivision of the integration interval [0,t ] into n subintervals [ti, tixe2x88x921], i=1, . . . n, t0 less than ti less than  . . .  less than txe2x89xa1t.
As described above, calculating a path of the integral ∫0TY(s)dBFBM(s) approximately requires a realization of the random variables xcex94BFBM(i):=[BFBM(ti)xe2x88x92BFBM(tixe2x88x921) ], i=1, . . . n in each case. The expected value, variance and covariance of these intercorrelated random numbers can be calculated from the formulas (1.3) and (1.4):
E(xcex94BFBM(i))=0,i=1, . . . , nxe2x80x83xe2x80x83(3.5)
Var(xcex94BFBM(i))=2xc2x7const|tixe2x88x92tixe2x88x921|xcex2+1,i=1. . . , nxe2x80x83xe2x80x83(3.6)
Cov(xcex94BFBM(i),xcex94BFBM(j))=constxc2x7|tjxe2x88x92ti|xcex2+1+|tjxe2x88x921xe2x88x92ti|xcex2+1+|tjxe2x88x92tixe2x88x921|62 +1xe2x88x92|tjxe2x88x921xe2x88x92tixe2x88x921|xcex2+1), i,j=1, . . . , nxe2x80x83xe2x80x83(3.7)
Since the random variables xcex94BFBM(i) represent increases in a Gaussian stochastic process, the random variable vector (xcex94BFBM(1), . . . , xcex94BFBM(n)) is an n-dimensional Gaussian-distributed random variable, and thus completely determined by the expected value, variance and covariance (in accordance with formulas (3.5) to (3.7)).
A batch method for respectively generating a realization of the correlated random variables xcex94BFBM(1), . . . , xcex94BFBM(n) is therefore as follows:
select a value of the coefficient const greater than 0 which parametrizes the intensity of the 1/f noise source generate a realization of an n-dimensional Gaussian normal distribution with the expected value 0 and covariance matrix
Covij=constxc2x7(xe2x88x92|tjxe2x88x92ti|xcex2+1+|tjxe2x88x921xe2x88x92ti|xcex2+1+|tjxe2x88x92tixe2x88x921|xcex2+1xe2x88x92|tjxe2x88x921xe2x88x92tixe2x88x921|xcex2+1)xe2x80x83xe2x80x83(3.8)
i,j=, . . . n.
interpret the random number vector thus generated as a realization of the sequence of BFBM increases {xcex94BFBM(1), . . . , xcex94BFBM(n)}, and use this realization as set forth above for the numerical calculation of a stochastic path for the time interval [0, t].
It may be pointed out that a dedicated realization of the sequence {xcex94BFBM(1), . . . , xcex94BFBM (n)} must be calculated for each 1/f noise source in the system.
If all elements of the covariance matrix C are determined, the non-calculated elements being occupied by the value 0, the result is an even rapid calculation. However, it is then necessary to accept limitations as regards the accuracy of the random numbers generated.
The invention is also implemented in a method for simulating a technical system which is subject to a 1/f noise, use being made when modeling and/or stipulating the variables present on input channels of the system of random numbers which have been determined using a method according to the invention.
A computer program is likewise provided for determining sequences of random numbers of a 1/f noise, and is designed such that the method according to the invention can be carried out. The invention is also implemented in a data medium having such a computer program. Furthermore, the invention is implemented in a method in the case of which a computer program according to the invention is downloaded from an electronic data network such as, for example, from the Internet onto a computer connected to the data network.
The invention is explained in the drawing with the aid of several exemplary embodiments.